#include "data_mode.h"

char d2c[] = "0123456789ABCDEF";
int ret19() { return rand()%9+1; }
int ret09() { return rand()%10; } // 0~9 的数字
int random(int n) { return (long long) rand() * rand() % n; } 
int random(int a, int b) { 
	if (a > b) return -1;
	if (a == b) return a;
	return random(b - a + 1) + a; 
}
 
LL retll(int n) { 
	LL s = 0; 
	for (int i=1; i<=n; i++) { 
		if (i==1) s = s*10 + ret19();
		else s = s*10 + ret09(); 
	} 
	return s; 
} // 随机 n 位数 

/*
无特征随机 
树（普通树） 
*/

// 基本可以用，还需要改 
void tree(vector<int> g[], int n, int max_m) {
	// n - 1 条边
	queue<int> q;
	q.push(1);
	int s = 2;
	int m = n - 1;
	 
	while (m > 0) {
		int u = q.front();
		q.pop();
		
		int en = random(0, min(rand() % (max_m + 1), m));
		
		while (q.size() == 0 && en == 0) en = random(1, min(rand() % (max_m + 1), m));
		m -= en;
		
		for(int i = 1; i <= en; s ++, i ++) {
			g[u].push_back(s);
			q.push(s);
		}
	} 
}

// 1 普通有向图
int graph(int direct, int wLow, int wHigh, int n, int m, int u[], int v[], int w[]) {
	int ret = 0;
	if (direct == 1 && m > n * (n - 1)) ret = -1; // 失败
	else if (direct == 0 && m > n * (n - 1) / 2) ret = -2; // 失败
	else if (wLow < 0) ret = -3;
	else if (direct > 1 || direct < 0 || wHigh < wLow || n <= 0 || m < 0) ret = -10; 
	switch(ret) {
		case -1: cout << "是有向图，但边太多了\n"; break;
		case -2: cout << "是无向图，但边太多了\n"; break;
		case -3: cout << "权值下界不可为负"; break;
		case -10: cout << "存在非法参数\n"; break;
	}
	if (ret < 0) return ret;
	
	// 无边权，w 则都为 1 
	// 边权 
	map<pair<int, int>, int> edge;
	
	int i;
	for (i = 1; i <= m; i ++) {
		int tu = random(1, n), tv = random(1, n);
		if (tu == tv) { i --; }
		else {
			pair<int, int> t = make_pair(tu, tv);
			pair<int, int> rt = make_pair(tv, tu); // 以备无向的判断
			
			if (edge.count(t)) i--;
			else {
				edge[t] = random(wLow, wHigh);
			} 
		} 
	} 
	
	i = 0;
	for (auto it : edge) {
		u[++i] = it.first.first;
		v[i] = it.first.second;
		w[i] = it.second;
	}
	
	return i;
} 

/*
void testTree() {
	int n = 20;
	vector<int> G[N];
	tree(G, n, n - 1);		
	for (int i = 1; i <= n; i ++) {
		printf("%d: ", i);
		for (int j = 0; j < G[i].size(); j ++) {
			cout << G[i][j] << ' ';
		}
		cout << endl;
	}
		
	cout << "===============================" << endl;
}


void testGragh() {
	
	// 起点终点边权 
	int *u = new int[M];
	int *v = new int[M];
	int *w = new int[M];
	
	// 顶点数量，边数量 
	int n = 10, m = 20;
	int ret = graph(1, 0, 20, n, m, u, v, w);
	cout << "ret: " << ret << endl;
	if (ret < 0) return ;
	
	// 有约 1/5 的负边权 
	int t = rand() % (int)ceil(m * 1.0 / 5) + 1;
	while (t -- ) {
		int i = rand() % m + 1;
		w[i] = -w[i];
	}
	
	// 乱序输入 
	int *order = new int[M];
	for (int i = 1; i <= m; i ++) order[i] = i;
	t = 1000;
	while (t--) {
		int x = rand() % m + 1, y = rand() % m + 1;
		swap(order[x], order[y]);
	}
	
	// 构建数据 
	for (int c = 1; c <= m; c ++) {
		int i = order[c];
		printf("%d %d %d\n", u[i], v[i], w[i]);
	}
	
	delete []u;
	delete []v;
	delete []w;
}

*/
